1223C - Save the Nature - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<int64_t> vll;

#define pb push_back
#define pob pop_back()
#define mp make_pair
#define sz size()
#define ff first
#define ss second
#define PI 3.14159265359
#define M1 ll(998244353)
#define M2 ll(1000000007)
#define pres(x) cout<<fixed; cout<<setprecision(x);
#define out(x) cout<<x<<endl;

ll gcd(ll a, ll b) {
    if (b > a) {return gcd(b, a);}
    if (b == 0) {return a;}
    return gcd(b, a % b);
}
int power(int a,int b){
    int ans=1;
    while(b!=0){
        if(b&1){ans=(ans*a)%M2;b--;}
        a=(a*a)%M2;b/=2;
    }
    return ans%M2;
}
ll expo(ll a, ll b, ll mod) {
    ll res = 1; 
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod; 
        b = b >> 1;
    } 
    return res;
}
int invmod(int n){
    int ans=1;
    ans=power(n,M2-2);
    return ans;
}
int lcm(int a,int b){
    int g=gcd(a,b);
    a/=g;a*=b;
    return a;
}

bool find(int num,vll &v,int x,int a,int y,int b,ll k,int lc){
    // int comm=num/lc;
    // int frst=(num/a)-comm;
    // int sec=(num/b)-comm;
    int comm=0,frst=0,sec=0;
    for(int i=1;i<=num;i++){
      if(i%a==0 && i%b==0) comm++;
      else if(i%a==0) frst++;
      else if(i%b==0) sec++;
    }
    int i=0;
    ll amnt=0;
    while(i<comm) amnt+=(x+y)*v[i++];
    while(i<(comm+frst)) amnt+=x*v[i++];
    while(i<(comm+frst+sec)) amnt+=y*v[i++];
    return amnt>=k;
}

void solve(){
    int n;
    cin>>n;
    vll v(n);
    for(int i=0;i<n;i++) {cin>>v[i];v[i]/=100;}
    sort(v.rbegin(),v.rend());
    int x,a;
    cin>>x>>a;
    int y,b;
    cin>>y>>b;
    if(x<y) {swap(x,y);swap(a,b);}
    ll k;
    cin>>k;
    int gc=__gcd(a,b);
    int lc=(a*1ll*b)/gc;
    int l=1,r=n;
    while(r-l>1){
        int mid=(l+r)/2;
        if(find(mid,v,x,a,y,b,k,lc)) r=mid;
        else l=mid+1;
    }
    if(find(l,v,x,a,y,b,k,lc)){
        out(l)
        return;
    }
    if(find(r,v,x,a,y,b,k,lc)){
        out(r)
        return;
    }
    // if(r>n) r=-1;
    out(-1)
    return;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}